This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Groups where the discrete logarithm problem is assumed to be intractable are central in the design of public-key cryptography. This was first pointed out by Diffie and Hellman in their seminal report: Whitfield Diffie and Martin E. Hellman, “New Directions in Cryptography”, IEEE, Transactions on Information Theory, 22(6):644-654, 1976.
The security of the Diffie-Hellman key-distribution system relies on the intractability of the discrete logarithm problem in the multiplicative group of finite fields. Such groups also enable the construction of encryption schemes, digital signature schemes, and many other cryptographic primitives and protocols; see Alfred J. Menezes, Paul C. van Oorchot, and Scott A. Vanstone, “Handbook of Applied Cryptography”, CRC Press, 1997.
Several solutions have been proposed to improve the efficiency of the so-obtained schemes.
Schnorr suggests working in a prime-order subgroup of px rather than in the whole group px; see Claus-Peter Schnorr, “Efficient Signature Generation by Smart Cards”. Journal of Cryptology, 4(3):161-174, 1991.
Lenstra extends this idea to the cyclotomic subgroup of pxr, stating that the underlying field is really pr and not some intermediate subfield; see Arjen K. Lenstra, “Using Cyclotomic Polynomials to Construct Efficient Discrete Logarithm Cryptosystems Over Finite Fields”, in V. V. Varadharajan, J. Pieprzyk, and Y. Mu, editors, Information Security and Privacy (ACISP '97), volume 1270 of Lecture Notes in Computer Science, pages 127-138. Springer-Verlag, 1997.
More recently, Rubin and Silverberg rephrased cyclotomic subgroups in terms of algebraic tori over p. The main advantage of their approach resides in the compact representation of the elements. See Karl Rubin and Alice Silverberg, Torus-Based Cryptography, In D. Boneh, editor, Advances in Cryptology—CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 349-365. Springer-Verlag, 2003.
Other prominent proposals featuring a compact representation include LUC (see Peter Smith and Christopher Skinner, “A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms”, In J. Pieprzyk and R. Safavi-Naini, editors, Advances in Cryptology—ASIACRYPT'94, volume 917 of Lecture Notes in Computer Science, pages 357-364. Springer-Verlag, 1995.) and XTR (see Arjen K. Lenstra and Eric R. Verheul, “The XTR public key system”. In M. Bellare, editor, Advances in Cryptology—CRYPTO 2000, volume 1880 of Lecture Notes in Computer Science, page 119. Springer-Verlag, 2000).
Variants of Diffie-Hellman key-distribution system in the multiplicative group Nx, where N is the product of two primes are proposed by Kevin S. McCurley (see “A key distribution system equivalent to factoring”, Journal of Cryptology, 1(2):95-105, 1988) and Zahava Shmuely (see “Composite Diffie-Hellman public key generating systems hard to break”, Technical Report 356, Israel Institute of Technology, Computer Science Department, Technion, February 1985). The goal is to combine the security of the original scheme with the difficulty of factoring large numbers. McCurley argues that it may be desirable to design cryptographic systems with the property that breaking them requires solving two different computational problems.